package com.atguigu.avl;

/**
 * @author shkstart
 * @create 2021-08-18 12:16
 */
public class AvlTreeDemo {
    public static void main(String[] args) {
        int[] arr = { 10, 11, 7, 6, 8, 9 };
        //创建平衡树
        AVLTree avlTree = new AVLTree();
        //添加节点
        for (int i=0;i<arr.length;i++){
            avlTree.add(new Node(arr[i]));
        }
        //遍历
        avlTree.infixOrder();
        System.out.println(avlTree.getRoot().height());
        System.out.println(avlTree.getRoot().leftHeight());
        System.out.println(avlTree.getRoot().rightHeight());
        System.out.println("根节点="+avlTree.getRoot());
        System.out.println("根节点的左节点="+avlTree.getRoot().left);
        System.out.println("根节点的左节点="+avlTree.getRoot().right);
    }
}
//创建二叉排序树
class AVLTree{
    private Node root;

    public void setRoot(Node root) {
        this.root = root;
    }

    public Node getRoot() {
        return root;
    }
    //删除最小的节点

    /**
     *
     * @param node 出入从哪里开始巡查，查找最小的节点
     * @return 返回最小节点的值
     */
    public int delRightTreeMin(Node node){
        //参数传递
        Node target=node;
        //不断向左循环，查找最小的值
        while (target.left!=null){
            target=target.left;
        }
        //删除值
        delNode(target.value);
        return target.value;
    }
    //删除节点
    public void delNode(int value){
        if (root==null){
            return;
        }
        //查找该节点
        Node targeNode = search(value);
        //如果该节点等于空
        if (targeNode==null){
            return;
        }
        //如果只留一个节点，还能走到这程序，那就说明该查找删除的节点就是根节点,并且这树只有一个节点
        if (root.left==null&&root.right==null){
            root=null;
            return;
        }
        //查找父节点
        Node parent = searchParent(value);
        //如果一个节点没有父节点，那只能是根节点
        //说明要查找删除的节点是根节点
//        if (parent==null){
//            root=null;
//            return;
//        }
        //删除叶子节点的情况
        //判断是否是叶子节点
        if (targeNode.left==null&&targeNode.right==null){
            if (parent.left!=null&&parent.left.value==value){
                parent.left=null;
            }else if (parent.right!=null&&parent.right.value==value){
                parent.right=null;

            }
        }//该节点有两个节点
        else if (targeNode.left!=null&targeNode.right!=null){
            //寻找该节点的右子树最小的节点值
            int minVal = delRightTreeMin(targeNode.right);
            //最小值来替代该节点
            targeNode.value=minVal;
        }
        else {//剩余只有一个节点的情况
            //只剩下一个左节点
            if (targeNode.left!=null){
                //如果该节点的父节点不为空
                if (parent!=null) {
                    //检查targeNode是父节点的左节点
                    if (parent.left.value == value) {
                        parent.left = targeNode.left;
                    } else {
                        //检查targeNode是父节点的右节点
                        parent.right = targeNode.left;
                    }
                }else {
                    root=targeNode.left;
                }
            }//若是剩下一个右节点
            else {
                if (parent!=null) {
                    if (parent.left.value == value) {
                        parent.left = targeNode.right;
                    } else {
                        parent.right = targeNode.right;
                    }
                }else {
                    root=targeNode.right;

                }
            }

        }
    }

    //查找要删除的节点
    public Node search(int value){
        if (root==null){
            return null;
        }else {
            return root.search(value);
        }
    }

    //查找要删除的父节点
    public Node searchParent(int value){
        if (root==null){
            return null;
        }else {
            return root.searchParent(value);
        }
    }

    //添加节点
    public void add(Node node){
        //如果节点为空，那就直接赋值
        if (root==null){
            root=node;
        }else {
            //如果不为空，那就只能不断循环
            root.add(node);
        }

    }
    //中序遍历
    public void infixOrder(){
        if (root!=null){
            root.infixOrder();
        }else {
            System.out.println("空树，无法遍历");
        }
    }
}

//创建节点
class Node{
    //值
    int value;
   Node left;
   Node right;
    //构造器


    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    //返回左子树的高度
    public int leftHeight(){
        if (left==null){
            return 0;
        }else {
            return left.height();
        }
    }

    //返回右子树的高度
    public int rightHeight(){
        if (right==null){
            return 0;
        }else {
            return right.height();
        }
    }
    //返回当前的节点的树的高度
    public int height(){
        return Math.max(left==null? 0:left.height(),right==null? 0: right.height())+1;
    }
    //右旋转
    private  void rightRotate(){
        Node newNode = new Node(value);
        newNode.right=right;
        newNode.left=left.right;
        value=left.value;
        left=left.left;
        right=newNode;
    }
  //左旋转：六大步骤
    private void leftRotate(){
        //创建的新节点，新节点值等于原来节点的值
        Node newNode = new Node(value);
        //新的节点的左节点设置位当前节点的左节点
        newNode.left=left;
        //新的节点的左节点设置位当前节点的右子树的左节点
        newNode.right=right.left;
        //当前节点的值设置为右节点的值
        value=right.value;
        //当前节点的右节点设置为右节点的右节点
        right=right.right;
        //当前节点的左节点设置为新的节点
        left=newNode;
    }
    //查找要删除的节点

    /**
     *
     * @param value 删除节点的值
     * @return 返回该查找的节点
     */
    public Node search(int value){
        //如果找到，直接输出
        if (value==this.value){
            return this;
        }else {
            //如果没有找到，分两种情况
            //1，value<当前节点
            if (value<this.value){
                //判断该节点的左节点是否为空
                if (this.left==null){
                    return null;
                }else {
                    //如果不为空，那就递归
                    return this.left.search(value);
                }
            }//如果value>当前节点
            else {
                if (this.right==null){
                    return null;
                }else {
                    return this.right.search(value);
                }

            }
        }
    }
    //查找要删除节点的父节点
    public Node searchParent(int value){
        if ((this.left!=null&&this.left.value==value)||
                (this.right!=null&&this.right.value==value)){
            return this;
        }else {
            //不断递归
            if (value<this.value&&this.left!=null){
                return this.left.searchParent(value);
            }else if (value>=this.value&&this.right!=null){
                return this.right.searchParent(value);
            }else {
                //一个节点没有父节点，例如根节点
                return null;
            }
        }
    }
    //添加节点
    //采用递归的方法
    public void add(Node node){
        //如果为空，那就退出
        if (node==null){
            return;
        }
        //如果加入的节点小于当前节点，那就往左边
        if (node.value<this.value){
            //如果该节点的左边没有节点，那就加入
            if (this.left==null){
                this.left=node;
            }else {
                //否则需要不断往左循环查找,递归
                this.left.add(node);
            }
        }//如果加入的节点大于当前节点，那就往右边
        else {
            if (this.right==null){
                this.right=node;
            }else {
                this.right.add(node);
            }

        }
        //如果添加节点，如果右子树的高度大于左子树的高度，那就左旋转
        if((rightHeight()-leftHeight())>1){
            //如果它的右子树的左子树的高度大于它的右子树的右子树的高度
            if (right!=null&&right.leftHeight()>right.rightHeight()){
                //先对右子结点进行右旋转
                right.rightRotate();
                //然后在对当前结点进行左旋转
                leftRotate();

            }else {
                //直接进行左旋转即可
                leftRotate();//左旋转
            }
            //处理完，记得退出
            return;//因为处理完已经平衡，无需接下来的操作
        }
        //如果添加节点，如果左子树的高度大于右子树的高度，那就右旋转
        if((leftHeight()-rightHeight())>1){
            //如果当前节点左子树的右节点大于左节点，那就左子树先进行左旋转
            if (left!=null&&left.rightHeight()>left.leftHeight()){
                //子树先进行左旋转
                left.leftRotate();
                //再对当前节点进行右旋转
                rightRotate();
            }else {
                //否则直接右旋转
                rightRotate();//右旋转
            }
        }
    }
    //中序遍历
    public void infixOrder(){
        if (this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }
    }
}